package pers.qianyu.month_202101.date_20210113;

import java.util.*;

/**
 * 756. 金字塔转换矩阵
 * https://leetcode-cn.com/problems/pyramid-transition-matrix/
 *
 * @author mizzle rain
 * @date 2021-01-13 20:57
 */
public class PyramidTransition {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        HashMap<String, List<Character>> map = new HashMap<>();
        for (String s : allowed) {
            String prefix = s.substring(0, 2);
            List<Character> list = map.getOrDefault(prefix, new ArrayList<>());
            list.add(s.charAt(2));
            map.put(prefix, list);
        }
        return dfs(bottom, "", map);
    }

    private boolean dfs(String bottom, String cur, HashMap<String, List<Character>> map) {
        if (bottom.length() == 1) return true;
        if (cur.length() == bottom.length() - 1) return dfs(cur, "", map);
        int i = cur.length();
        while (i < bottom.length() - 1) {
            String sub = bottom.substring(i, i + 2);
            List<Character> chs = map.get(sub);
            if (chs == null) return false;
            for (Character ch : chs) {
                if (dfs(bottom, cur + ch, map)) return true;
            }
            i++;
        }
        return false;
    }
}
